package edu.dayu.demo3;

import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * 给定一个数组，计算不相邻数和的最大值。
 * 输入：nums = [1,2,3,1]
 * 输出：4
 * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 *      偷窃到的最高金额 = 1 + 3 = 4
 * 思路： 题目的意思是不能拿相邻的，但是也没说不能空两个。
 *       1、用 一个数组保存到第 i 家最多偷多少钱。
 *
 */
public class 房屋偷盗 {
    public static void main(String[] args) {
        int[] nums = {2,4,8,9,9,3};
        System.out.println(rob(nums));
    }

    public static int rob(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n+1];
        dp[1] = nums[0];
        for (int i = 2; i < n+1; i++) {
            dp[i] = Math.max(dp[i-2]+nums[i-1], dp[i-1]);
        }
        return dp[n];
    }
}
